class Solution:
    # 从i向前找 找到nums[j+1]+...nums[i]<=x的最小j
    def find(self,nums, i, x):
        if nums[i] == x:
            return i
        else:
            for j in range(i, -1, -1):
                if sum(nums[j:i + 1]) > x:
                    return j
            return -1
    def getAns(self,x,nums):
        n = len(nums)
        dp = [0] * (n)  # dp[i]=m： 0-i个元素共有m种方案
        dp[0] = 1
        for i in range(1, n):
            if nums[i] == x:  # nums[i]只能自成一组，组合数不变
                dp[i] = dp[i - 1]
            else:
                # nums[j+1]+nums[j+1]+....+nums[i]<=x  那么可以是nums[i]成一组 这个时候方案数是dp[i-1]; 或者nums[i-1],nums[i]成一组，组合数是dp[i-2]；
                # 直到nums[j+1].....nums[i]成一组，组合数是 dp[j]
                j = self.find(nums, i, x)
                if j == -1:
                    dp[i] = 1
                    dp[i] += sum(dp[0:i])

                else:
                    dp[i] = sum(dp[j:i])
        return dp[-1]
S = Solution()
nums = [5,5,5]
print(S.getAns(5,nums))
nums = [5,5,3]
print(S.getAns(10,nums))


